Spiral matrix ii

Time: O(N^2); Space: O(1); medium

Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

Example 1

Input: n = 3

Output:

[
    [ 1, 2, 3 ],
    [ 8, 9, 4 ],
    [ 7, 6, 5 ]
]

class Solution1(object):

    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        matrix = [[0 for _ in range(n)] for _ in range(n)]

        left, right, top, bottom, num = 0, n - 1, 0, n - 1, 1

        while left <= right and top <= bottom:
            for j in range(left, right + 1):
                matrix[top][j] = num
                num += 1
            for i in range(top + 1, bottom):
                matrix[i][right] = num
                num += 1
            for j in reversed(range(left, right + 1)):
                if top < bottom:
                    matrix[bottom][j] = num
                    num += 1
            for i in reversed(range(top + 1, bottom)):
                if left < right:
                    matrix[i][left] = num
                    num += 1
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1

        return matrix

s = Solution1()
n = 3
assert s.generateMatrix(n) == [
        [ 1, 2, 3 ],
        [ 8, 9, 4 ],
        [ 7, 6, 5 ]
    ]
n = 8
assert s.generateMatrix(n) ==[
    [1, 2, 3, 4, 5, 6, 7, 8],
    [28, 29, 30, 31, 32, 33, 34, 9],
    [27, 48, 49, 50, 51, 52, 35, 10],
    [26, 47, 60, 61, 62, 53, 36, 11],
    [25, 46, 59, 64, 63, 54, 37, 12],
    [24, 45, 58, 57, 56, 55, 38, 13],
    [23, 44, 43, 42, 41, 40, 39, 14],
    [22, 21, 20, 19, 18, 17, 16, 15]
]

See also:

https://leetcode.com/problems/spiral-matrix-ii/

https://www.lintcode.com/problem/spiral-matrix-ii